home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / gnustuff / tos / g__~1 / gplibs15.zoo / xfix.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1992-10-01  |  12.5 KB  |  621 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /*
  3. Copyright (C) 1989 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18. //
  19. // Fix.cc : variable length fixed point data type class functions
  20. //
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <xfix.h>
  26. #include <std.h>
  27. #include <xobstack.h>
  28. #include <xallocri.h>
  29. #include <strstrea.h>
  30.  
  31. // default parameters
  32.  
  33. uint16 Fix_default_length = 16;
  34. int    Fix_default_print_width = 8;
  35.  
  36. Fix_peh Fix_overflow_handler = Fix_overflow_saturate;
  37.  
  38. _Frep _Frep_0    = { 16, 1, 1, { 0 } };
  39. _Frep _Frep_m1    = { 16, 1, 1, { 0x8000 } };
  40. _Frep _Frep_quotient_bump = { 16, 1, 1, { 0x4000 } };
  41.  
  42. // error handling
  43.  
  44. void default_Fix_error_handler(const char* msg)
  45. {
  46.   cerr << "Fix: " << msg << "\n";
  47.   abort();
  48. }
  49.  
  50. void default_Fix_range_error_handler(const char* msg)
  51. {
  52.   cerr << "Fix: range error in " << msg << "\n";
  53.   //abort();
  54. }
  55.  
  56. one_arg_error_handler_t 
  57.   Fix_error_handler = default_Fix_error_handler,
  58.   Fix_range_error_handler = default_Fix_range_error_handler;
  59.  
  60. one_arg_error_handler_t set_Fix_error_handler(one_arg_error_handler_t f)
  61. {
  62.   one_arg_error_handler_t old = Fix_error_handler;
  63.   Fix_error_handler = f;
  64.   return old;
  65. }
  66.  
  67. one_arg_error_handler_t set_Fix_range_error_handler(one_arg_error_handler_t f)
  68. {
  69.   one_arg_error_handler_t old = Fix_range_error_handler;
  70.   Fix_range_error_handler = f;
  71.   return old;
  72. }
  73.  
  74. void Fix::error(const char* msg)
  75. {
  76.   (*Fix_error_handler)(msg);
  77. }
  78.  
  79. void Fix::range_error(const char* msg)
  80. {
  81.   (*Fix_range_error_handler)(msg);
  82. }
  83.  
  84. // _Frep allocation and initialization functions
  85.  
  86. static inline _Fix _new_Fix(uint16 len)
  87. {
  88.   int siz = (((uint32 )len + 15) >> 4);
  89.   if (siz <= 0) siz = 1;
  90.   size_t allocsiz = (sizeof(_Frep) + (siz - 1) * sizeof(uint16));
  91.   _Fix z = (_Fix)(new char[allocsiz]);
  92.   bzero(z, allocsiz);
  93.   z->len = len;
  94.   z->siz = siz;
  95.   z->ref = 1;
  96.   return z;
  97. }
  98.  
  99. _Fix new_Fix(uint16 len)
  100. {
  101.   return _new_Fix(len);
  102. }
  103.  
  104. _Fix new_Fix(uint16 len, _Fix x)
  105. {
  106.   _Fix z = _new_Fix(len);
  107.   return copy(x,z);
  108. }
  109.  
  110. _Fix new_Fix(uint16 len, double d)
  111. {
  112.   _Fix z = _new_Fix(len);
  113.  
  114.   if ( d == _Fix_max_value )
  115.   {
  116.     z->s[0] = 0x7fff;
  117.     for ( int i=1; i < z->siz; i++ )
  118.       z->s[i] = 0xffff;
  119.   }
  120.   else if ( d < _Fix_min_value || d > _Fix_max_value )
  121.     (*Fix_range_error_handler)("declaration");
  122.   else
  123.   {
  124.     if (d < 0)
  125.       d += 2.0;
  126.     d *= 32768;
  127.     for ( int i=0; i < z->siz; i++ )
  128.     {
  129.       z->s[i] = (uint16 )d;
  130.       d -= z->s[i];
  131.       d *= 65536;
  132.     }
  133.     if ( d >= 32768 )
  134.       z->s[z->siz-1]++;
  135.   }
  136.   mask(z);
  137.   return z;
  138. }
  139.  
  140. // convert to a double 
  141.  
  142. double value(Fix& x)
  143. { 
  144.   double d = 0.0;
  145.   for ( int i=x.rep->siz-1; i >= 0; i-- )
  146.   {
  147.     d += x.rep->s[i];
  148.     d *= 1./65536.;
  149.   }
  150.   d *= 2.;
  151.   return d < 1. ? d : d - 2.;
  152. }
  153.  
  154. // extract mantissa to Integer
  155.  
  156. Integer mantissa(Fix& x)
  157. {
  158.   Integer a = 1, b=1;
  159.   for ( int i=0; i < x.rep->siz; i++ )
  160.   {
  161.     a = (a << 16) + x.rep->s[i];
  162.     b <<= 16;
  163.   }
  164.   return a-b;
  165. }
  166.  
  167. // comparison functions
  168.   
  169. inline static int docmp(uint16* x, uint16* y, int siz)
  170. {
  171.   int diff = (int16 )*x - (int16 )*y;
  172.   while ( --siz && !diff )
  173.     diff = (int32 )(uint32 )*++x - (int32 )(uint32 )*++y;
  174.   return diff;
  175. }
  176.  
  177. inline static int docmpz(uint16* x, int siz)
  178. {
  179.   while ( siz-- )
  180.     if ( *x++ ) return 1;
  181.   return 0;
  182. }
  183.  
  184. int compare(_Fix x, _Fix y)
  185. {
  186.   if ( x->siz == y->siz )
  187.     return docmp(x->s, y->s, x->siz);
  188.   else
  189.   {
  190.     int r;
  191.     _Fix longer, shorter;
  192.     if ( x->siz > y->siz )
  193.     {
  194.       longer = x;
  195.       shorter = y;
  196.       r = 1;
  197.     }
  198.     else
  199.     {
  200.       longer = y;
  201.       shorter = x;
  202.       r = -1;
  203.     }
  204.     int diff = docmp(x->s, y->s, shorter->siz);
  205.     if ( diff )
  206.       return diff;
  207.     else if ( docmpz(&longer->s[shorter->siz], longer->siz-shorter->siz) )
  208.       return r;
  209.     else
  210.       return 0;
  211.   }
  212. }
  213.  
  214. // arithmetic functions
  215.  
  216. _Fix add(_Fix x, _Fix y, _Fix r)
  217. {
  218.   uint16 xsign = x->s[0], ysign = y->s[0];
  219.   _Fix longer, shorter;
  220.   if ( x->len >= y->len )
  221.     longer = x, shorter = y;
  222.   else
  223.     longer = y, shorter = x;
  224.   if ( r == NULL )
  225.     r = new_Fix(longer->len);
  226.   for ( int i=r->siz-1; i >= longer->siz; i-- )
  227.     r->s[i] = 0;
  228.   for ( ; i >= shorter->siz; i-- )
  229.     r->s[i] = longer->s[i];
  230.   uint32 sum = 0, carry = 0;
  231.   for ( ; i >= 0; i-- )
  232.   {
  233.     sum = carry + (uint32 )x->s[i] + (uint32 )y->s[i];
  234.     carry = sum >> 16;
  235.     r->s[i] = sum;
  236.   }
  237.   if ( (xsign ^ sum) & (ysign ^ sum) & 0x8000 )
  238.     (*Fix_overflow_handler)(r);
  239.   return r;
  240. }
  241.  
  242. _Fix subtract(_Fix x, _Fix y, _Fix r)
  243. {
  244.   uint16 xsign = x->s[0], ysign = y->s[0];
  245.   _Fix longer, shorter;
  246.   if ( x->len >= y->len )
  247.     longer = x, shorter = y;
  248.   else
  249.     longer = y, shorter = x;
  250.   if ( r == NULL )
  251.     r = new_Fix(longer->len);
  252.   for ( int i=r->siz-1; i >= longer->siz; i-- )
  253.     r->s[i] = 0;
  254.   for ( ; i >= shorter->siz; i-- )
  255.     r->s[i] = (longer == x ? x->s[i] : -y->s[i]);
  256.   int16 carry = 0;
  257.   uint32 sum = 0;
  258.   for ( ; i >= 0; i-- )
  259.   {
  260.     sum = (int32 )carry + (uint32 )x->s[i] - (uint32 )y->s[i];
  261.     carry = sum >> 16;
  262.     r->s[i] = sum;
  263.   }
  264.   if ( (xsign ^ sum) & (~ysign ^ sum) & 0x8000 )
  265.     (*Fix_overflow_handler)(r);
  266.   return r;
  267. }
  268.  
  269. _Fix multiply(_Fix x, _Fix y, _Fix r)
  270. {
  271.   if ( r == NULL )
  272.     r = new_Fix(x->len + y->len);
  273.   int xsign = x->s[0] & 0x8000,
  274.     ysign = y->s[0] & 0x8000;
  275.   Fix X(x->len), Y(y->len);
  276.   if ( xsign )
  277.     x = negate(x,X.rep);
  278.   if ( ysign )
  279.     y = negate(y,Y.rep);
  280.   for ( int i=0; i < r->siz; i++ )
  281.     r->s[i] = 0;
  282.   for ( i=x->siz-1; i >= 0; i-- )
  283.   {
  284.     uint32 carry = 0;
  285.     for ( int j=y->siz-1; j >= 0; j-- ) 
  286.     {
  287.       int k = i + j + 1;
  288.       uint32 a = (uint32 )x->s[i] * (uint32 )y->s[j];
  289.       uint32 b = ((a << 1) & 0xffff) + carry;
  290.       if ( k < r->siz )
  291.       {
  292.     b += r->s[k];
  293.         r->s[k] = b;
  294.       }
  295.       if ( k < r->siz + 1 )
  296.         carry = (a >> 15) + (b >> 16);
  297.     }
  298.     r->s[i] = carry;
  299.   }
  300.   if ( xsign != ysign )
  301.     negate(r,r);
  302.   return r;
  303. }
  304.  
  305. _Fix multiply(_Fix x, int y, _Fix r)
  306. {
  307.   if ( y != (int16 )y )
  308.     (*Fix_range_error_handler)("multiply by int -- int too large");
  309.   if ( r == NULL )
  310.     r = new_Fix(x->len);
  311.   for ( int i=r->siz-1; i >= x->siz; i-- )
  312.     r->s[i] = 0;
  313.   int32 a, carry = 0;
  314.   for ( ; i > 0; i-- )
  315.   {
  316.     a = (int32 )(uint32 )x->s[i] * y + carry;
  317.     r->s[i] = a;
  318.     carry = a >> 16;        // assumes arithmetic right shift
  319.   }
  320.   a = (int32 )(int16 )x->s[0] * y + carry;
  321.   r->s[0] = a;
  322.   a &= 0xffff8000L;
  323.   if ( a != 0xffff8000L && a != 0L ) {
  324.     r->s[0] = 0x8000 ^ x->s[0] ^ y;
  325.     (*Fix_overflow_handler)(r);
  326.   }
  327.   return r;
  328. }
  329.  
  330. _Fix divide(_Fix x, _Fix y, _Fix q, _Fix r)
  331. {
  332.   int xsign = x->s[0] & 0x8000, 
  333.     ysign = y->s[0] & 0x8000;
  334.   if ( q == NULL )
  335.     q = new_Fix(x->len);
  336.   copy(&_Frep_0,q);
  337.   if ( r == NULL )
  338.     r = new_Fix(x->len + y->len - 1);
  339.   if ( xsign )
  340.     negate(x,r);
  341.   else
  342.     copy(x,r);
  343.   Fix Y(y->len);
  344.   y = ( ysign ? negate(y,Y.rep) : copy(y,Y.rep) );
  345.   if ( !compare(y) )
  346.     (*Fix_range_error_handler)("division -- division by zero");
  347.   else if ( compare(x,y) >= 0 )
  348.     if ( compare(x,y) == 0 && (xsign ^ ysign) != 0 )
  349.     {
  350.       copy(&_Frep_m1,q);
  351.       copy(&_Frep_0,r);
  352.     }
  353.     else
  354.       (*Fix_range_error_handler)("division");
  355.   else
  356.   {
  357.     _Fix t;
  358.     Fix S(r->len),
  359.       W(q->len,&_Frep_quotient_bump);
  360.     for ( int i=1; i < q->len; i++ )
  361.     {
  362.       shift(y,-1,y);
  363.       subtract(r,y,S.rep);
  364.       int s_status = compare(S.rep);
  365.       if ( s_status == 0 ) 
  366.       {
  367.     t = r, r = S.rep, S.rep = t;
  368.     break;
  369.       }
  370.       else if ( s_status > 0 )
  371.       {
  372.     t = r, r = S.rep, S.rep = t;
  373.     add(q,W.rep,q);
  374.       }
  375.       shift(W.rep,-1,W.rep);
  376.     }
  377.     if ( xsign ^ ysign )
  378.       negate(q,q);
  379.   }
  380.   return q;
  381. }
  382.  
  383. _Fix shift(_Fix x, int y, _Fix r)
  384. {
  385.   if ( y == 0 )
  386.     return x;
  387.   else if ( r == NULL )
  388.     r = new_Fix(x->len);
  389.  
  390.   int ay = abs((long) y),
  391.     ayh = ay >> 4,
  392.     ayl = ay & 0x0f;
  393.   int xl, u, ilow, ihigh;
  394.   uint16 *rs, *xsl, *xsr;
  395.  
  396.   if ( y > 0 )
  397.   {
  398.     rs = r->s;
  399.     xsl = x->s + ayh;
  400.     xsr = xsl + 1;
  401.     xl = ayl;
  402.     u = 1;
  403.     ihigh = x->siz - ayh - 1;
  404.     ilow = 0;
  405.   }
  406.   else
  407.   {
  408.     rs = &r->s[r->siz - 1];
  409.     xsr = &x->s[r->siz - 1] - ayh;
  410.     xsl = xsr - 1;
  411.     xl = 16 - ayl;
  412.     u = -1;
  413.     ihigh = r->siz - ayh - 1;
  414.     ilow = ihigh - x->siz;
  415.   }
  416.  
  417.   int xr = 16 - xl;
  418.   uint16 xrmask = 0xffffL >> xr;
  419.   for ( int i=0; i < ilow; i++, rs+=u, xsl+=u, xsr+=u )
  420.     *rs = 0;
  421.   for ( ; i < ihigh; i++, rs+=u, xsl+=u, xsr+=u )
  422.     *rs = (*xsl << xl) + ((*xsr >> xr) & xrmask);
  423.   *rs = (y > 0 ? (*xsl << xl) : ((*xsr >> xr) & xrmask));
  424.   rs += u;
  425.   for ( ; ++i < r->siz; rs+=u )
  426.     *rs = 0;
  427.   return r;
  428. }
  429.  
  430. _Fix negate(_Fix x, _Fix r)
  431. {
  432.   if ( r == NULL )
  433.     r = new_Fix(x->len);
  434.   uint32 carry = 1;
  435.   for ( int i=r->siz-1; i >= x->siz; i-- )
  436.     r->s[i] = 0;
  437.   for ( ; i >= 0; i-- )
  438.   {
  439.     uint32 a = (uint16 )~x->s[i] + carry;    // bug work-around
  440.     r->s[i] = a;
  441.     carry = a >> 16;
  442.   }
  443.   return r;
  444. }
  445.  
  446. // io functions
  447.  
  448. Fix atoF(const char* a, int len)
  449. {
  450.   return Fix(len,atof(a));
  451. }
  452.  
  453. extern AllocRing _libgxx_fmtq;
  454.  
  455. void Fix::printon(ostream& s, int width)
  456. {
  457.   char format[20];
  458.   double val = value(*this);
  459.   int old_precision = s.precision(width-3);
  460.   ios::fmtflags old_flags = s.setf(ios::fixed, ios::fixed|ios::scientific);
  461.   if (val >= 0)
  462.       s << ' ';
  463.   s.width(width-2);
  464.   s << val;
  465.   s.precision(old_precision);
  466.   s.flags(old_flags);
  467. }
  468.  
  469. char* Ftoa(Fix& x, int width)
  470. {
  471.   int wrksiz = width + 2;
  472.   char *fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  473.   ostrstream stream(fmtbase, wrksiz);
  474.   
  475.   x.printon(stream, width);
  476.   stream << ends;
  477.   return fmtbase;
  478. }
  479.  
  480. extern Obstack _libgxx_io_ob;
  481.  
  482. Fix Fix::operator %= (int y)
  483. {
  484.   Fix r((int )rep->len + y, *this); return *this = r;
  485. }
  486.  
  487. istream& operator >> (istream& s, Fix& y)
  488. {
  489.   int got_one = 0;
  490. #ifdef _OLD_STREAMS
  491.   if (!s.good())
  492.   {
  493.     return s;
  494.   }
  495. #else
  496.   if (!s.ipfx(0))
  497.   {
  498.     s.set(ios::failbit); // Redundant if using GNU iostreams.
  499.     return s;
  500.   }
  501. #endif
  502.  
  503.   char sign = 0, point = 0;
  504.   char ch;
  505.   s >> ws;
  506.   if (!s.good())
  507.   {
  508.     s.set(_fail);
  509.     return s;
  510.   }
  511.   while (s.get(ch))
  512.   {
  513.     if (ch == '-')
  514.     {
  515.       if (sign == 0)
  516.       {
  517.         sign = 1;
  518.         _libgxx_io_ob.grow(ch);
  519.       }
  520.       else
  521.         break;
  522.     }
  523.     if (ch == '.')
  524.     {
  525.       if (point == 0)
  526.       {
  527.         point = 1;
  528.         _libgxx_io_ob.grow(ch);
  529.       }
  530.       else
  531.         break;
  532.     }
  533.     else if (ch >= '0' && ch <= '9')
  534.     {
  535.       got_one = 1;
  536.       _libgxx_io_ob.grow(ch);
  537.     }
  538.     else
  539.       break;
  540.   }
  541.   char * p = (char*)(_libgxx_io_ob.finish(0));
  542.   if (s.good())
  543.     s.putback(ch);
  544.   if (!got_one)
  545.     s.set(_fail);
  546.   else
  547.     y = atoF(p);
  548.   _libgxx_io_ob.free(p);
  549.   return s;
  550. }
  551.  
  552. void show(Fix& x)
  553. {
  554.   cout << "len = " << x.rep->len << "\n";
  555.   cout << "siz = " << x.rep->siz << "\n";
  556.   cout << "ref = " << x.rep->ref << "\n";
  557.   cout << "man = ";
  558. #ifdef _OLD_STREAMS
  559.   cout << Itoa(mantissa(x),16,4*x.rep->siz);
  560. #else
  561.   int old_flags = cout.setf(ios::hex, ios::hex|ios::dec|ios::oct);
  562.   cout.width(4*x.rep->siz);
  563.   cout << mantissa(x);
  564.   cout.setf(old_flags, ios::hex|ios::dec|ios::oct);
  565. #endif
  566.   cout << "\n";
  567.   cout << "val = " << value(x) << "\n";
  568. }
  569.  
  570. // parameter setting operations
  571.  
  572. Fix_peh set_overflow_handler(Fix_peh new_handler) {
  573.   Fix_peh old_handler = Fix_overflow_handler;
  574.   Fix_overflow_handler = new_handler;
  575.   return old_handler;
  576. }
  577.  
  578. int Fix_set_default_length(int newlen)
  579. {
  580.   uint16 oldlen = Fix_default_length;
  581.   if ( newlen < _Fix_min_length || newlen > _Fix_max_length )
  582.     (*Fix_error_handler)("illegal length in Fix_set_default_length");
  583.   Fix_default_length = newlen;
  584.   return oldlen;
  585. }
  586.  
  587. // overflow handlers
  588.  
  589. void Fix_overflow_saturate(_Fix& r) {
  590.   if ( (int16 )r->s[0] > 0 ) 
  591.   {
  592.     r->s[0] = 0x8000;
  593.     for ( int i=1; i < r->siz; i++ )
  594.       r->s[i] = 0;
  595.   }
  596.   else
  597.   {
  598.     r->s[0] = 0x7fff;
  599.     for ( int i=1; i < r->siz; i++ )
  600.       r->s[i] = 0xffff;
  601.     mask(r);
  602.   }
  603. }
  604.  
  605. void Fix_overflow_wrap(_Fix& r) {}
  606.  
  607. void Fix_overflow_warning_saturate(_Fix& r) {
  608.   Fix_overflow_warning(r);
  609.   Fix_overflow_saturate(r);
  610. }
  611.  
  612. void Fix_overflow_warning(_Fix& r) {
  613.   cerr << "Fix: overflow warning\n"; 
  614. }
  615.  
  616. void Fix_overflow_error(_Fix& r) {
  617.   cerr << "Fix: overflow error\n"; 
  618.   abort();
  619. }
  620.  
  621.